{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Louvain Community Detection\n",
    "\n",
    "\n",
    "In this notebook, we will use cuGraph to identify the cluster in a test graph using the Louvain algorithm  \n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees and James Wyles\n",
    "* Created:   08/01/2019\n",
    "* Last Edit: 05/27/2020\n",
    "\n",
    "RAPIDS Versions: 0.14\n",
    "\n",
    "Test Hardware\n",
    "* GV100 32G, CUDA 10.2\n",
    "\n",
    "\n",
    "\n",
    "## Introduction\n",
    "\n",
    "The Louvain method of community detection is a greedy hierarchical clustering algorithm which seeks to optimize Modularity as it progresses. Louvain starts with each vertex in its own clusters and iteratively merges groups using graph contraction.  \n",
    "\n",
    "For a detailed description of the algorithm see: https://en.wikipedia.org/wiki/Louvain_Modularity\n",
    "\n",
    "It takes as input a cugraph.Graph object and returns as output a \n",
    "cudf.Dataframe object with the id and assigned partition for each \n",
    "vertex as well as the final modularity score\n",
    "\n",
    "To compute the Louvain cluster in cuGraph use: <br>\n",
    "   __df, mod  = cugraph.louvain(G, max_iter = 100)__\n",
    "   \n",
    "  \n",
    "    Parameters\n",
    "    ----------\n",
    "    input_graph : cugraph.Graph\n",
    "        cuGraph graph descriptor, should contain the connectivity information\n",
    "        as an edge list. The adjacency list will be computed if not already present.\n",
    "        The graph should be undirected where an undirected edge is represented by a\n",
    "        directed edge in both direction.\n",
    "\n",
    "    max_iter : integer\n",
    "        This controls the maximum number of levels/iterations of the Louvain\n",
    "        algorithm. When specified the algorithm will terminate after no more\n",
    "        than the specified number of iterations. No error occurs when the\n",
    "        algorithm terminates early in this manner.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    parts : cudf.DataFrame\n",
    "        A GPU data frame of size V containing two columns the vertex id and the\n",
    "        partition id it is assigned to.\n",
    "        \n",
    "            df[‘vertex’] cudf.Series\n",
    "                Contains the vertex identifiers\n",
    "            df[‘partition’] cudf.Series\n",
    "                Contains the partition assigned to the vertices\n",
    "        \n",
    "        \n",
    "    modularity_score : float\n",
    "        a floating point number containing the modularity score of the\n",
    "        partitioning.\n",
    "        \n",
    "    All vertices with the same partition ID are in the same cluster\n",
    "        \n",
    "\n",
    "\n",
    "#### Note\n",
    "Parallel Louvain produces different modularity scores that serial Louvain.\n",
    "\n",
    "Serial Louvain is a greedy method that iterates over the vertices in numerical order and\n",
    "evaluates whether to move a vertex into a different cluster and then moves it if\n",
    "modularity is increased.  After considering all vertices in serial it computes a new\n",
    "modularity score and if better than the last clustering it will repeat.  If vertex i is\n",
    "moved to a new cluster, and vertex j is a neighbor of vertex i and is processed after\n",
    "vertex i, then vertex j will compute its delta modularity based on the vertex i's new\n",
    "cluster assignment.\n",
    "\n",
    "Parallel Louvain computes delta modularity for all vertex/cluster combinations and chooses\n",
    "the best change for ALL vertices in parallel.  This means that vertex i and vertex j being\n",
    "neighbors (as above), both will see the old cluster assignment for that vertex.  This will result\n",
    "in different decisions being made between the parallel and serial versions.  Because Louvain\n",
    "is a greedy method, those decisions might lead the algorithms to converge on different local\n",
    "maximums.\n",
    "\n",
    "A complete technical write-up is being produced and will be linked here when available.  \n",
    "\n",
    "### References\n",
    "* Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008, 10 (2008), P10008.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](../img/zachary_black_lines.png)\n",
    "\n",
    "The test data has vertex IDs strating at 1.  We will be using the auto-renumber feature of cuGraph to renumber the data so that the starting vertex ID is zero.  The data will be auto-unrenumbered so that the renumbering step is transparent to users. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Read data using cuDF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file    \n",
    "datafile='../data//karate-data.csv'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read the data using cuDF\n",
    "gdf = cudf.read_csv(datafile, delimiter='\\t', names=['src', 'dst'], dtype=['int32', 'int32'] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The algorithm also requires that there are vertex weights.  Just use 1.0 \n",
    "gdf[\"data\"] = 1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# just for fun, let's look at the data types in the dataframe\n",
    "gdf.dtypes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph - since the data does not start at '0', use the auto-renumbering feature\n",
    "G = cugraph.Graph()\n",
    "G.from_cudf_edgelist(gdf, source='src', destination='dst', edge_attr='data', renumber=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call Louvain on the graph\n",
    "df, mod = cugraph.louvain(G) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Print the modularity score\n",
    "print('Modularity was {}'.format(mod))\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.dtypes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# How many partitions where found\n",
    "part_ids = df[\"partition\"].unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(str(len(part_ids)) + \" partition detected\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print the clusters.  \n",
    "for p in range(len(part_ids)):\n",
    "    part = []\n",
    "    for i in range(len(df)):\n",
    "        if (df['partition'].iloc[i] == p):\n",
    "            part.append(df['vertex'].iloc[i] )\n",
    "    print(\"Partition \" + str(p) + \":\")\n",
    "    print(part)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019-2020, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
